10734 - Triangle Partitioning/p10734.cpp

   1 #include <iostream>
   2 #include <math.h>
   3 #include <vector>
   4 using namespace std;
   5
   6 vector<vector<double> > t;
   7
   8 bool semejantes(const vector<double> &t1, const vector<double> &t2){
   9   return (t1[0]/t2[0] == t1[1]/t2[1] &&
  10           t1[1]/t2[1] == t1[2]/t2[2] &&
  11           t1[2]/t2[2] == t1[0]/t2[0] );
  12 }
  13
  14 void divide(vector<double> v){
  15   sort(v.begin(), v.end());
  16   double h = sqrt(2*v[1]*v[1]-v[2]*v[2]+2*v[0]*v[0])/2;
  17
  18   vector<double> h1(3), h2(3);
  19   h1[0] = h2[0] = h;
  20   h1[1] = h2[1] = v[2]/2;
  21   h1[2] = v[0];
  22   h2[2] = v[1];
  23   sort(h1.begin(), h1.end());
  24   sort(h2.begin(), h2.end());
  25
  26   bool yaEsta = true;
  27   for (int i=0; i<t.size(); ++i){
  28     yaEsta = yaEsta && !(semejantes(h1, t[i]));
  29   }
  30   if (!yaEsta){
  31     t.push_back(h1);
  32     divide(h1);
  33   }
  34
  35   yaEsta = true;
  36   for (int i=0; i<t.size(); ++i){
  37     yaEsta = yaEsta && !(semejantes(h2, t[i]));
  38   }
  39   if (!yaEsta){
  40     t.push_back(h2);
  41     divide(h2);
  42   }
  43 }
  44
  45 int main(){
  46   int n;
  47   scanf("%d", &n);
  48   for (int i=1; i<=n; ++i){
  49     t.clear();
  50     vector<double> temp(3);
  51     for (int j=0; j<3; ++j){
  52       cin >> temp[i];
  53     }
  54     divide(temp);
  55     cout << t.size() << endl;
  56
  57   }
  58   return 0;
  59 }